package com.aplink.generic.google.maps.clustering.view;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import android.animation.Animator;
import android.animation.AnimatorListenerAdapter;
import android.animation.TimeInterpolator;
import android.animation.ValueAnimator;
import android.annotation.SuppressLint;
import android.annotation.TargetApi;
import android.content.Context;
import android.graphics.Color;
import android.graphics.drawable.Drawable;
import android.graphics.drawable.LayerDrawable;
import android.graphics.drawable.ShapeDrawable;
import android.graphics.drawable.shapes.OvalShape;
import android.os.Build;
import android.os.Handler;
import android.os.Looper;
import android.os.Message;
import android.os.MessageQueue;
import android.util.SparseArray;
import android.view.ViewGroup;
import android.view.animation.DecelerateInterpolator;

import com.aplink.generic.google.maps.MarkerManager;
import com.aplink.generic.google.maps.clustering.Cluster;
import com.aplink.generic.google.maps.clustering.ClusterItem;
import com.aplink.generic.google.maps.clustering.ClusterManager;
import com.aplink.generic.google.maps.clustering.algo.NonHierarchicalDistanceBasedAlgorithm;
import com.aplink.generic.google.maps.geometry.Point;
import com.aplink.generic.google.maps.projection.SphericalMercatorProjection;
import com.aplink.generic.google.maps.ui.IconGenerator;
import com.aplink.generic.google.maps.ui.SquareTextView;
import com.aplink.sg.R;
import com.google.android.gms.maps.GoogleMap;
import com.google.android.gms.maps.Projection;
import com.google.android.gms.maps.model.BitmapDescriptor;
import com.google.android.gms.maps.model.BitmapDescriptorFactory;
import com.google.android.gms.maps.model.LatLng;
import com.google.android.gms.maps.model.LatLngBounds;
import com.google.android.gms.maps.model.Marker;
import com.google.android.gms.maps.model.MarkerOptions;

/**
 * The default view for a ClusterManager. Markers are animated in and out of
 * clusters.
 */
public class DefaultClusterRenderer<T extends ClusterItem> implements
        ClusterRenderer<T> {
    /**
     * Animates a markerWithPosition from one position to another. TODO: improve
     * performance for slow devices (e.g. Nexus S).
     */
    @TargetApi(Build.VERSION_CODES.HONEYCOMB_MR1)
    private class AnimationTask extends AnimatorListenerAdapter implements
            ValueAnimator.AnimatorUpdateListener {
        private final LatLng from;
        private final Marker marker;
        private final MarkerWithPosition markerWithPosition;
        private MarkerManager mMarkerManager;
        private boolean mRemoveOnComplete;
        private final LatLng to;

        private AnimationTask(final MarkerWithPosition markerWithPosition,
                final LatLng from, final LatLng to) {
            this.markerWithPosition = markerWithPosition;
            this.marker = markerWithPosition.marker;
            this.from = from;
            this.to = to;
        }

        @Override
        public void onAnimationEnd(final Animator animation) {
            if (mRemoveOnComplete) {
                mMarkerCache.remove(marker);
                mMarkerToCluster.remove(marker);
                mMarkerManager.remove(marker);
            }
            markerWithPosition.position = to;
        }

        @Override
        public void onAnimationUpdate(final ValueAnimator valueAnimator) {
            final float fraction = valueAnimator.getAnimatedFraction();
            final double lat = ((to.latitude - from.latitude) * fraction)
                    + from.latitude;
            double lngDelta = to.longitude - from.longitude;

            // Take the shortest path across the 180th meridian.
            if (Math.abs(lngDelta) > 180) {
                lngDelta -= Math.signum(lngDelta) * 360;
            }
            final double lng = (lngDelta * fraction) + from.longitude;
            final LatLng position = new LatLng(lat, lng);
            marker.setPosition(position);
        }

        public void perform() {
            final ValueAnimator valueAnimator = ValueAnimator.ofFloat(0, 1);
            valueAnimator
                    .setInterpolator(DefaultClusterRenderer.ANIMATION_INTERP);
            valueAnimator.addUpdateListener(this);
            valueAnimator.addListener(this);
            valueAnimator.start();
        }

        public void removeOnAnimationComplete(final MarkerManager markerManager) {
            mMarkerManager = markerManager;
            mRemoveOnComplete = true;
        }
    }

    /**
     * Creates markerWithPosition(s) for a particular cluster, animating it if
     * necessary.
     */
    private class CreateMarkerTask {
        private final LatLng animateFrom;
        private final Cluster<T> cluster;
        private final Set<MarkerWithPosition> newMarkers;

        /**
         * @param c
         *            the cluster to render.
         * @param markersAdded
         *            a collection of markers to append any created markers.
         * @param animateFrom
         *            the location to animate the markerWithPosition from, or
         *            null if no animation is required.
         */
        public CreateMarkerTask(final Cluster<T> c,
                final Set<MarkerWithPosition> markersAdded,
                final LatLng animateFrom) {
            this.cluster = c;
            this.newMarkers = markersAdded;
            this.animateFrom = animateFrom;
        }

        private void perform(final MarkerModifier markerModifier) {
            // Don't show small clusters. Render the markers inside, instead.
            if (!shouldRenderAsCluster(cluster)) {
                for (final T item : cluster.getItems()) {
                    Marker marker = mMarkerCache.get(item);
                    MarkerWithPosition markerWithPosition;
                    if (marker == null) {
                        final MarkerOptions markerOptions = new MarkerOptions();
                        if (animateFrom != null) {
                            markerOptions.position(animateFrom);
                        } else {
                            markerOptions.position(item.getPosition());
                        }
                        onBeforeClusterItemRendered(item, markerOptions);
                        marker = mClusterManager.getMarkerCollection()
                                .addMarker(markerOptions);
                        markerWithPosition = new MarkerWithPosition(marker);
                        mMarkerCache.put(item, marker);
                        if (animateFrom != null) {
                            markerModifier.animate(markerWithPosition,
                                    animateFrom, item.getPosition());
                        }
                    } else {
                        markerWithPosition = new MarkerWithPosition(marker);
                    }
                    onClusterItemRendered(item, marker);
                    newMarkers.add(markerWithPosition);
                }
                return;
            }

            final MarkerOptions markerOptions = new MarkerOptions()
                    .position(animateFrom == null ? cluster.getPosition()
                            : animateFrom);

            onBeforeClusterRendered(cluster, markerOptions);

            final Marker marker = mClusterManager.getClusterMarkerCollection()
                    .addMarker(markerOptions);
            mMarkerToCluster.put(marker, cluster);
            final MarkerWithPosition markerWithPosition = new MarkerWithPosition(
                    marker);
            if (animateFrom != null) {
                markerModifier.animate(markerWithPosition, animateFrom,
                        cluster.getPosition());
            }
            onClusterRendered(cluster, marker);
            newMarkers.add(markerWithPosition);
        }
    }

    /**
     * A cache of markers representing individual ClusterItems.
     */
    private static class MarkerCache<T> {
        private final Map<T, Marker> mCache = new HashMap<T, Marker>();
        private final Map<Marker, T> mCacheReverse = new HashMap<Marker, T>();

        public T get(final Marker m) {
            return mCacheReverse.get(m);
        }

        public Marker get(final T item) {
            return mCache.get(item);
        }

        public void put(final T item, final Marker m) {
            mCache.put(item, m);
            mCacheReverse.put(m, item);
        }

        public void remove(final Marker m) {
            final T item = mCacheReverse.get(m);
            mCacheReverse.remove(m);
            mCache.remove(item);
        }
    }

    /**
     * Handles all markerWithPosition manipulations on the map. Work (such as
     * adding, removing, or animating a markerWithPosition) is performed while
     * trying not to block the rest of the app's UI.
     */
    @SuppressLint("HandlerLeak")
    private class MarkerModifier extends Handler implements
            MessageQueue.IdleHandler {
        private static final int BLANK = 0;
        private final Lock lock = new ReentrantLock();
        private final Condition busyCondition = lock.newCondition();
        private final Queue<AnimationTask> mAnimationTasks = new LinkedList<AnimationTask>();
        private final Queue<CreateMarkerTask> mCreateMarkerTasks = new LinkedList<CreateMarkerTask>();
        /**
         * Whether the idle listener has been added to the UI thread's
         * MessageQueue.
         */
        private boolean mListenerAdded;
        private final Queue<CreateMarkerTask> mOnScreenCreateMarkerTasks = new LinkedList<CreateMarkerTask>();
        private final Queue<Marker> mOnScreenRemoveMarkerTasks = new LinkedList<Marker>();

        private final Queue<Marker> mRemoveMarkerTasks = new LinkedList<Marker>();

        private MarkerModifier() {
            super(Looper.getMainLooper());
        }

        /**
         * Creates markers for a cluster some time in the future.
         * 
         * @param priority
         *            whether this operation should have priority.
         */
        public void add(final boolean priority, final CreateMarkerTask c) {
            lock.lock();
            sendEmptyMessage(MarkerModifier.BLANK);
            if (priority) {
                mOnScreenCreateMarkerTasks.add(c);
            } else {
                mCreateMarkerTasks.add(c);
            }
            lock.unlock();
        }

        /**
         * Animates a markerWithPosition some time in the future.
         * 
         * @param marker
         *            the markerWithPosition to animate.
         * @param from
         *            the position to animate from.
         * @param to
         *            the position to animate to.
         */
        public void animate(final MarkerWithPosition marker, final LatLng from,
                final LatLng to) {
            lock.lock();
            mAnimationTasks.add(new AnimationTask(marker, from, to));
            lock.unlock();
        }

        /**
         * Animates a markerWithPosition some time in the future, and removes it
         * when the animation is complete.
         * 
         * @param marker
         *            the markerWithPosition to animate.
         * @param from
         *            the position to animate from.
         * @param to
         *            the position to animate to.
         */
        public void animateThenRemove(final MarkerWithPosition marker,
                final LatLng from, final LatLng to) {
            lock.lock();
            final AnimationTask animationTask = new AnimationTask(marker, from,
                    to);
            animationTask.removeOnAnimationComplete(mClusterManager
                    .getMarkerManager());
            mAnimationTasks.add(animationTask);
            lock.unlock();
        }

        @Override
        public void handleMessage(final Message msg) {
            if (!mListenerAdded) {
                Looper.myQueue().addIdleHandler(this);
                mListenerAdded = true;
            }
            removeMessages(MarkerModifier.BLANK);

            lock.lock();
            try {

                // Perform up to 10 tasks at once.
                // Consider only performing 10 remove tasks, not adds and
                // animations.
                // Removes are relatively slow and are much better when batched.
                for (int i = 0; i < 10; i++) {
                    performNextTask();
                }

                if (!isBusy()) {
                    mListenerAdded = false;
                    Looper.myQueue().removeIdleHandler(this);
                    // Signal any other threads that are waiting.
                    busyCondition.signalAll();
                } else {
                    // Sometimes the idle queue may not be called - schedule up
                    // some work regardless
                    // of whether the UI thread is busy or not.
                    // TODO: try to remove this.
                    sendEmptyMessageDelayed(MarkerModifier.BLANK, 10);
                }
            } finally {
                lock.unlock();
            }
        }

        /**
         * @return true if there is still work to be processed.
         */
        public boolean isBusy() {
            return !(mCreateMarkerTasks.isEmpty()
                    && mOnScreenCreateMarkerTasks.isEmpty()
                    && mOnScreenRemoveMarkerTasks.isEmpty()
                    && mRemoveMarkerTasks.isEmpty() && mAnimationTasks
                        .isEmpty());
        }

        /**
         * Perform the next task. Prioritise any on-screen work.
         */
        private void performNextTask() {
            if (!mOnScreenRemoveMarkerTasks.isEmpty()) {
                removeMarker(mOnScreenRemoveMarkerTasks.poll());
            } else if (!mAnimationTasks.isEmpty()) {
                mAnimationTasks.poll().perform();
            } else if (!mOnScreenCreateMarkerTasks.isEmpty()) {
                mOnScreenCreateMarkerTasks.poll().perform(this);
            } else if (!mCreateMarkerTasks.isEmpty()) {
                mCreateMarkerTasks.poll().perform(this);
            } else if (!mRemoveMarkerTasks.isEmpty()) {
                removeMarker(mRemoveMarkerTasks.poll());
            }
        }

        @Override
        public boolean queueIdle() {
            // When the UI is not busy, schedule some work.
            sendEmptyMessage(MarkerModifier.BLANK);
            return true;
        }

        /**
         * Removes a markerWithPosition some time in the future.
         * 
         * @param priority
         *            whether this operation should have priority.
         * @param m
         *            the markerWithPosition to remove.
         */
        public void remove(final boolean priority, final Marker m) {
            lock.lock();
            sendEmptyMessage(MarkerModifier.BLANK);
            if (priority) {
                mOnScreenRemoveMarkerTasks.add(m);
            } else {
                mRemoveMarkerTasks.add(m);
            }
            lock.unlock();
        }

        private void removeMarker(final Marker m) {
            mMarkerCache.remove(m);
            mMarkerToCluster.remove(m);
            mClusterManager.getMarkerManager().remove(m);
        }

        /**
         * Blocks the calling thread until all work has been processed.
         */
        public void waitUntilFree() {
            while (isBusy()) {
                // Sometimes the idle queue may not be called - schedule up some
                // work regardless
                // of whether the UI thread is busy or not.
                // TODO: try to remove this.
                sendEmptyMessage(MarkerModifier.BLANK);
                lock.lock();
                try {
                    if (isBusy()) {
                        busyCondition.await();
                    }
                } catch (final InterruptedException e) {
                    throw new RuntimeException(e);
                } finally {
                    lock.unlock();
                }
            }
        }
    }

    /**
     * A Marker and its position. Marker.getPosition() must be called from the
     * UI thread, so this object allows lookup from other threads.
     */
    private static class MarkerWithPosition {
        private final Marker marker;
        private LatLng position;

        private MarkerWithPosition(final Marker marker) {
            this.marker = marker;
            position = marker.getPosition();
        }

        @Override
        public boolean equals(final Object other) {
            if (other instanceof MarkerWithPosition) {
                return marker.equals(((MarkerWithPosition) other).marker);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return marker.hashCode();
        }
    }

    /**
     * Transforms the current view (represented by
     * DefaultClusterRenderer.mClusters and DefaultClusterRenderer.mZoom) to a
     * new zoom level and set of clusters.
     * <p/>
     * This must be run off the UI thread. Work is coordinated in the
     * RenderTask, then queued up to be executed by a MarkerModifier.
     * <p/>
     * There are three stages for the render:
     * <p/>
     * 1. Markers are added to the map
     * <p/>
     * 2. Markers are animated to their final position
     * <p/>
     * 3. Any old markers are removed from the map
     * <p/>
     * When zooming in, markers are animated out from the nearest existing
     * cluster. When zooming out, existing clusters are animated to the nearest
     * new cluster.
     */
    private class RenderTask implements Runnable {
        final Set<? extends Cluster<T>> clusters;
        private Runnable mCallback;
        private float mMapZoom;
        private Projection mProjection;
        private SphericalMercatorProjection mSphericalMercatorProjection;

        private RenderTask(final Set<? extends Cluster<T>> clusters) {
            this.clusters = clusters;
        }

        @Override
        @SuppressLint("NewApi")
        public void run() {
            if (clusters.equals(DefaultClusterRenderer.this.mClusters)) {
                mCallback.run();
                return;
            }

            final MarkerModifier markerModifier = new MarkerModifier();

            final float zoom = mMapZoom;
            final boolean zoomingIn = zoom > mZoom;
            final float zoomDelta = zoom - mZoom;

            final Set<MarkerWithPosition> markersToRemove = mMarkers;
            final LatLngBounds visibleBounds = mProjection.getVisibleRegion().latLngBounds;
            // TODO: Add some padding, so that markers can animate in from
            // off-screen.

            // Find all of the existing clusters that are on-screen. These are
            // candidates for
            // markers to animate from.
            List<Point> existingClustersOnScreen = null;
            if ((DefaultClusterRenderer.this.mClusters != null)
                    && DefaultClusterRenderer.SHOULD_ANIMATE) {
                existingClustersOnScreen = new ArrayList<Point>();
                for (final Cluster<T> c : DefaultClusterRenderer.this.mClusters) {
                    if (shouldRenderAsCluster(c)
                            && visibleBounds.contains(c.getPosition())) {
                        final Point point = mSphericalMercatorProjection
                                .toPoint(c.getPosition());
                        existingClustersOnScreen.add(point);
                    }
                }
            }

            // Create the new markers and animate them to their new positions.
            final Set<MarkerWithPosition> newMarkers = new HashSet<MarkerWithPosition>();
            for (final Cluster<T> c : clusters) {
                final boolean onScreen = visibleBounds
                        .contains(c.getPosition());
                if (zoomingIn && onScreen
                        && DefaultClusterRenderer.SHOULD_ANIMATE) {
                    final Point point = mSphericalMercatorProjection.toPoint(c
                            .getPosition());
                    final Point closest = DefaultClusterRenderer
                            .findClosestCluster(existingClustersOnScreen, point);
                    if (closest != null) {
                        final LatLng animateTo = mSphericalMercatorProjection
                                .toLatLng(closest);
                        markerModifier.add(true, new CreateMarkerTask(c,
                                newMarkers, animateTo));
                    } else {
                        markerModifier.add(true, new CreateMarkerTask(c,
                                newMarkers, null));
                    }
                } else {
                    markerModifier.add(onScreen, new CreateMarkerTask(c,
                            newMarkers, null));
                }
            }

            // Wait for all markers to be added.
            markerModifier.waitUntilFree();

            // Don't remove any markers that were just added. This is basically
            // anything that had
            // a hit in the MarkerCache.
            markersToRemove.removeAll(newMarkers);

            // Find all of the new clusters that were added on-screen. These are
            // candidates for
            // markers to animate from.
            List<Point> newClustersOnScreen = null;
            if (DefaultClusterRenderer.SHOULD_ANIMATE) {
                newClustersOnScreen = new ArrayList<Point>();
                for (final Cluster<T> c : clusters) {
                    if (shouldRenderAsCluster(c)
                            && visibleBounds.contains(c.getPosition())) {
                        final Point p = mSphericalMercatorProjection.toPoint(c
                                .getPosition());
                        newClustersOnScreen.add(p);
                    }
                }
            }

            // Remove the old markers, animating them into clusters if zooming
            // out.
            for (final MarkerWithPosition marker : markersToRemove) {
                final boolean onScreen = visibleBounds
                        .contains(marker.position);
                // Don't animate when zooming out more than 3 zoom levels.
                // TODO: drop animation based on speed of device & number of
                // markers to animate.
                if (!zoomingIn && (zoomDelta > -3) && onScreen
                        && DefaultClusterRenderer.SHOULD_ANIMATE) {
                    final Point point = mSphericalMercatorProjection
                            .toPoint(marker.position);
                    final Point closest = DefaultClusterRenderer
                            .findClosestCluster(newClustersOnScreen, point);
                    if (closest != null) {
                        final LatLng animateTo = mSphericalMercatorProjection
                                .toLatLng(closest);
                        markerModifier.animateThenRemove(marker,
                                marker.position, animateTo);
                    } else {
                        markerModifier.remove(true, marker.marker);
                    }
                } else {
                    markerModifier.remove(onScreen, marker.marker);
                }
            }

            markerModifier.waitUntilFree();

            mMarkers = newMarkers;
            DefaultClusterRenderer.this.mClusters = clusters;
            mZoom = zoom;

            mCallback.run();
        }

        /**
         * A callback to be run when all work has been completed.
         * 
         * @param callback
         */
        public void setCallback(final Runnable callback) {
            mCallback = callback;
        }

        public void setMapZoom(final float zoom) {
            this.mMapZoom = zoom;
            this.mSphericalMercatorProjection = new SphericalMercatorProjection(
                    256 * Math.pow(2, Math.min(zoom, mZoom)));
        }

        public void setProjection(final Projection projection) {
            this.mProjection = projection;
        }
    }

    /**
     * ViewModifier ensures only one re-rendering of the view occurs at a time,
     * and schedules re-rendering, which is performed by the RenderTask.
     */
    @SuppressLint("HandlerLeak")
    private class ViewModifier extends Handler {
        private static final int RUN_TASK = 0;
        private static final int TASK_FINISHED = 1;
        private RenderTask mNextClusters = null;
        private boolean mViewModificationInProgress = false;

        @Override
        public void handleMessage(final Message msg) {
            if (msg.what == ViewModifier.TASK_FINISHED) {
                mViewModificationInProgress = false;
                if (mNextClusters != null) {
                    // Run the task that was queued up.
                    sendEmptyMessage(ViewModifier.RUN_TASK);
                }
                return;
            }
            removeMessages(ViewModifier.RUN_TASK);

            if (mViewModificationInProgress) {
                // Busy - wait for the callback.
                return;
            }

            if (mNextClusters == null) {
                // Nothing to do.
                return;
            }

            RenderTask renderTask;
            synchronized (this) {
                renderTask = mNextClusters;
                mNextClusters = null;
                mViewModificationInProgress = true;
            }

            renderTask.setCallback(new Runnable() {
                @Override
                public void run() {
                    sendEmptyMessage(ViewModifier.TASK_FINISHED);
                }
            });
            renderTask.setProjection(mMap.getProjection());
            renderTask.setMapZoom(mMap.getCameraPosition().zoom);
            new Thread(renderTask).start();
        }

        public void queue(final Set<? extends Cluster<T>> clusters) {
            synchronized (this) {
                // Overwrite any pending cluster tasks - we don't care about
                // intermediate states.
                mNextClusters = new RenderTask(clusters);
            }
            sendEmptyMessage(ViewModifier.RUN_TASK);
        }
    }

    private static final TimeInterpolator ANIMATION_INTERP = new DecelerateInterpolator();

    private static final int[] BUCKETS = { 10, 20, 50, 100, 200, 500, 1000 };

    /**
     * If cluster size is less than this size, display individual markers.
     */
    private static final int MIN_CLUSTER_SIZE = 4;

    private static final boolean SHOULD_ANIMATE = Build.VERSION.SDK_INT >= Build.VERSION_CODES.HONEYCOMB;

    private static double distanceSquared(final Point a, final Point b) {
        return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
    }

    private static Point findClosestCluster(final List<Point> markers,
            final Point point) {
        if ((markers == null) || markers.isEmpty()) {
            return null;
        }

        // TODO: make this configurable.
        double minDistSquared = NonHierarchicalDistanceBasedAlgorithm.MAX_DISTANCE_AT_ZOOM
                * NonHierarchicalDistanceBasedAlgorithm.MAX_DISTANCE_AT_ZOOM;
        Point closest = null;
        for (final Point candidate : markers) {
            final double dist = DefaultClusterRenderer.distanceSquared(
                    candidate, point);
            if (dist < minDistSquared) {
                closest = candidate;
                minDistSquared = dist;
            }
        }
        return closest;
    }

    private ClusterManager.OnClusterClickListener<T> mClickListener;

    private final ClusterManager<T> mClusterManager;

    /**
     * The currently displayed set of clusters.
     */
    private Set<? extends Cluster<T>> mClusters;
    private ShapeDrawable mColoredCircleBackground;
    private final float mDensity;
    private final IconGenerator mIconGenerator;

    /**
     * Icons for each bucket.
     */
    private final SparseArray<BitmapDescriptor> mIcons = new SparseArray<BitmapDescriptor>();

    private ClusterManager.OnClusterInfoWindowClickListener<T> mInfoWindowClickListener;

    private ClusterManager.OnClusterItemClickListener<T> mItemClickListener;

    private ClusterManager.OnClusterItemInfoWindowClickListener<T> mItemInfoWindowClickListener;

    private final GoogleMap mMap;

    /**
     * Markers for single ClusterItems.
     */
    private final MarkerCache<T> mMarkerCache = new MarkerCache<T>();

    /**
     * Markers that are currently on the map.
     */
    private Set<MarkerWithPosition> mMarkers = new HashSet<MarkerWithPosition>();

    /**
     * Lookup between markers and the associated cluster.
     */
    private final Map<Marker, Cluster<T>> mMarkerToCluster = new HashMap<Marker, Cluster<T>>();

    private final ViewModifier mViewModifier = new ViewModifier();

    /**
     * The target zoom level for the current set of clusters.
     */
    private float mZoom;

    public DefaultClusterRenderer(final Context context, final GoogleMap map,
            final ClusterManager<T> clusterManager) {
        mMap = map;
        mDensity = context.getResources().getDisplayMetrics().density;
        mIconGenerator = new IconGenerator(context);
        mIconGenerator.setContentView(makeSquareTextView(context));
        mIconGenerator.setTextAppearance(R.style.ClusterIcon_TextAppearance);
        mIconGenerator.setBackground(makeClusterBackground());
        mClusterManager = clusterManager;
    }

    /**
     * Gets the "bucket" for a particular cluster. By default, uses the number
     * of points within the cluster, bucketed to some set points.
     */
    protected int getBucket(final Cluster<T> cluster) {
        final int size = cluster.getSize();
        if (size <= DefaultClusterRenderer.BUCKETS[0]) {
            return size;
        }
        for (int i = 0; i < (DefaultClusterRenderer.BUCKETS.length - 1); i++) {
            if (size < DefaultClusterRenderer.BUCKETS[i + 1]) {
                return DefaultClusterRenderer.BUCKETS[i];
            }
        }
        return DefaultClusterRenderer.BUCKETS[DefaultClusterRenderer.BUCKETS.length - 1];
    }

    protected String getClusterText(final int bucket) {
        if (bucket < DefaultClusterRenderer.BUCKETS[0]) {
            return String.valueOf(bucket);
        }
        return String.valueOf(bucket) + "+";
    }

    private int getColor(final int clusterSize) {
        final float hueRange = 220;
        final float sizeRange = 300;
        final float size = Math.min(clusterSize, sizeRange);
        final float hue = (((sizeRange - size) * (sizeRange - size)) / (sizeRange * sizeRange))
                * hueRange;
        return Color.HSVToColor(new float[] { hue, 1f, .6f });
    }

    private LayerDrawable makeClusterBackground() {
        mColoredCircleBackground = new ShapeDrawable(new OvalShape());
        final ShapeDrawable outline = new ShapeDrawable(new OvalShape());
        outline.getPaint().setColor(0x80ffffff); // Transparent white.
        final LayerDrawable background = new LayerDrawable(new Drawable[] {
                outline, mColoredCircleBackground });
        final int strokeWidth = (int) (mDensity * 3);
        background.setLayerInset(1, strokeWidth, strokeWidth, strokeWidth,
                strokeWidth);
        return background;
    }

    private SquareTextView makeSquareTextView(final Context context) {
        final SquareTextView squareTextView = new SquareTextView(context);
        final ViewGroup.LayoutParams layoutParams = new ViewGroup.LayoutParams(
                ViewGroup.LayoutParams.WRAP_CONTENT,
                ViewGroup.LayoutParams.WRAP_CONTENT);
        squareTextView.setLayoutParams(layoutParams);
        squareTextView.setId(R.id.text);
        final int twelveDpi = (int) (12 * mDensity);
        squareTextView.setPadding(twelveDpi, twelveDpi, twelveDpi, twelveDpi);
        return squareTextView;
    }

    @Override
    public void onAdd() {
        mClusterManager.getMarkerCollection().setOnMarkerClickListener(
                new GoogleMap.OnMarkerClickListener() {
                    @Override
                    public boolean onMarkerClick(final Marker marker) {
                        return (mItemClickListener != null)
                                && mItemClickListener
                                        .onClusterItemClick(mMarkerCache
                                                .get(marker));
                    }
                });

        mClusterManager.getMarkerCollection().setOnInfoWindowClickListener(
                new GoogleMap.OnInfoWindowClickListener() {
                    @Override
                    public void onInfoWindowClick(final Marker marker) {
                        if (mItemInfoWindowClickListener != null) {
                            mItemInfoWindowClickListener
                                    .onClusterItemInfoWindowClick(mMarkerCache
                                            .get(marker));
                        }
                    }
                });

        mClusterManager.getClusterMarkerCollection().setOnMarkerClickListener(
                new GoogleMap.OnMarkerClickListener() {
                    @Override
                    public boolean onMarkerClick(final Marker marker) {
                        return (mClickListener != null)
                                && mClickListener
                                        .onClusterClick(mMarkerToCluster
                                                .get(marker));
                    }
                });

        mClusterManager.getClusterMarkerCollection()
                .setOnInfoWindowClickListener(
                        new GoogleMap.OnInfoWindowClickListener() {
                            @Override
                            public void onInfoWindowClick(final Marker marker) {
                                if (mInfoWindowClickListener != null) {
                                    mInfoWindowClickListener
                                            .onClusterInfoWindowClick(mMarkerToCluster
                                                    .get(marker));
                                }
                            }
                        });
    }

    /**
     * Called before the marker for a ClusterItem is added to the map.
     */
    protected void onBeforeClusterItemRendered(final T item,
            final MarkerOptions markerOptions) {
    }

    /**
     * Called before the marker for a Cluster is added to the map. The default
     * implementation draws a circle with a rough count of the number of items.
     */
    protected void onBeforeClusterRendered(final Cluster<T> cluster,
            final MarkerOptions markerOptions) {
        final int bucket = getBucket(cluster);
        BitmapDescriptor descriptor = mIcons.get(bucket);
        if (descriptor == null) {
            mColoredCircleBackground.getPaint().setColor(getColor(bucket));
            descriptor = BitmapDescriptorFactory.fromBitmap(mIconGenerator
                    .makeIcon(getClusterText(bucket)));
            mIcons.put(bucket, descriptor);
        }
        // TODO: consider adding anchor(.5, .5) (Individual markers will overlap
        // more often)
        markerOptions.icon(descriptor);
    }

    /**
     * Called after the marker for a ClusterItem has been added to the map.
     */
    protected void onClusterItemRendered(final T clusterItem,
            final Marker marker) {
    }

    /**
     * Called after the marker for a Cluster has been added to the map.
     */
    protected void onClusterRendered(final Cluster<T> cluster,
            final Marker marker) {
    }

    @Override
    public void onClustersChanged(final Set<? extends Cluster<T>> clusters) {
        mViewModifier.queue(clusters);
    }

    @Override
    public void onRemove() {
        mClusterManager.getMarkerCollection().setOnMarkerClickListener(null);
        mClusterManager.getClusterMarkerCollection().setOnMarkerClickListener(
                null);
    }

    @Override
    public void setOnClusterClickListener(
            final ClusterManager.OnClusterClickListener<T> listener) {
        mClickListener = listener;
    }

    @Override
    public void setOnClusterInfoWindowClickListener(
            final ClusterManager.OnClusterInfoWindowClickListener<T> listener) {
        mInfoWindowClickListener = listener;
    }

    @Override
    public void setOnClusterItemClickListener(
            final ClusterManager.OnClusterItemClickListener<T> listener) {
        mItemClickListener = listener;
    }

    @Override
    public void setOnClusterItemInfoWindowClickListener(
            final ClusterManager.OnClusterItemInfoWindowClickListener<T> listener) {
        mItemInfoWindowClickListener = listener;
    }

    /**
     * Determine whether the cluster should be rendered as individual markers or
     * a cluster.
     */
    protected boolean shouldRenderAsCluster(final Cluster<T> cluster) {
        return cluster.getSize() > DefaultClusterRenderer.MIN_CLUSTER_SIZE;
    }
}
